#pragma once
namespace key {
	template<class K>
	struct BSTNode
	{
		K _key;
		BSTNode<K>* _left;
		BSTNode<K>* _right;

		BSTNode(const K& key)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{
		}
	};

	template<class K>
	class BSTTree {
		typedef BSTNode<K> Node;
	public:
		bool InsertR(const K& key) {
			return _Insert(_root,key);
		}
		bool Insert(const K& key) {
			if (_root == nullptr) {
				_root = new Node(key);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key >key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					return false;
				}
			}
			cur = new Node(key);
			if (parent->_key < key) {
				parent->_right = cur;
			}
			else if (parent->_key>key){
				parent->_left = cur;
			}
			return true;
		}
		bool Find(const K& key) {
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					return true;
				}
			}
			return false;
		}
		bool Erasse(const K& key) {
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					if (cur->_left == nullptr || cur->_right==nullptr) {
						if (cur->_left == nullptr) {
							if (cur == _root) {
								_root = _root->_right;
								return true;
							}
							if (cur == parent->_left) {
								parent->_left = cur->_right;
							}
							else {
								parent->_right = cur->_right;
							}
							delete cur;
						}
						else {
							if (cur == _root) {
								_root = _root->_left;
								return true;
							}
							if (cur == parent->_left) {
								parent->_left = cur->_left;
							}
							else {
								parent->_right = cur->_left;
							}
							delete cur;
						}
					}
					else {
						Node* minrightparent = cur;
						Node* minright = cur->_right;
						while (minright->_left) {
							minrightparent = minright;
							minright = minright->_left;
						}
						swap(cur->_key, minright->_key);
						if (minright==minrightparent->_left)
							minrightparent->_left = minright->_right;
						else {
							minrightparent->_right = minright->_right;
						}
						delete minright;
					}
					return true;
				}
			}
			return false;
		}
		void InOrder() {
			_InOrder(_root);
		}
	private:
		void _Insert(Node*& root,const K& x) {
			if (root == nullptr) {
				root = new Node(x);
				return true;
			}

			if (root->_key < x) {
				return _Insert(root->_left, x);
			}
			else if (root->_key > x) {
				return _Insert(root->_right, x);
			}
			else {
				return false;
			}
		}
		void _InOrder(Node* root) {
			if (root == nullptr) {
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
	private:
		Node * _root = nullptr;
	};
}


namespace key_value {
	template<class K,class V>
	struct BSTNode
	{
		K _key;
		V _value;
		BSTNode<K,V>* _left;
		BSTNode<K,V>* _right;

		BSTNode(const K& key,const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{
		}
	};

	template<class K,class V>
	class BSTTree {
		typedef BSTNode<K,V> Node;
	public:
		bool Insert(const K& key,const V& value) {
			if (_root == nullptr) {
				_root = new Node(key,value);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					return false;
				}
			}
			cur = new Node(key,value);
			if (parent->_key < key) {
				parent->_right = cur;
			}
			else if (parent->_key > key) {
				parent->_left = cur;
			}
			return true;
		}
		Node* Find(const K& key) {
			Node* cur = _root;
			while (cur) {
				if (cur->_key < key) {
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					cur = cur->_left;
				}
				else {
					return cur;
				}
			}
			return nullptr;
		}
		bool Erasse(const K& key) {
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					if (cur->_left == nullptr || cur->_right == nullptr) {
						if (cur->_left == nullptr) {
							if (cur == _root) {
								_root = _root->_right;
								return true;
							}
							if (cur == parent->_left) {
								parent->_left = cur->_right;
							}
							else {
								parent->_right = cur->_right;
							}
							delete cur;
						}
						else {
							if (cur == _root) {
								_root = _root->_left;
								return true;
							}
							if (cur == parent->_left) {
								parent->_left = cur->_left;
							}
							else {
								parent->_right = cur->_left;
							}
							delete cur;
						}
					}
					else {
						Node* minrightparent = cur;
						Node* minright = cur->_right;
						while (minright->_left) {
							minrightparent = minright;
							minright = minright->_left;
						}
						swap(cur->_key, minright->_key);
						if (minright == minrightparent->_left)
							minrightparent->_left = minright->_right;
						else {
							minrightparent->_right = minright->_right;
						}
						delete minright;
					}
					return true;
				}
			}
			return false;
		}
		void InOrder() {
			_InOrder(_root);
		}
	private:
		void _InOrder(Node* root) {
			if (root == nullptr) {
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << ":"<<root->_value<<" ";
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};
}